\section{Discusi\'on}

En esta sección detallaremos el funcionamiento de la aplicación función por función, para que pueda servir de guía para el entendimiento del código, ademas de explicar lo hecho junto con problemas y decisiones tomadas.




\vspace{1cm}

\subsection{comprimir\_archivo}


Descripción dada por la cátedra:
\begin{itemize}
	\item Dado un archivo de entrada, lo carga en un buffer, lo comprime y
lo guarda en el archivo de salida (el archivo de salida consta de: a) un header, b)
los códigos utilizados para la codificación y c) los datos comprimidos). En caso de
no poder realizar la compresiión debe retornar un código de error.

\end{itemize}

Descripción del algoritmo: \\

El primer paso del algoritmo es abrir el archivo de entrada y almacenarlo en un buffer para poder codificarlo. Se abre el archivo usando la función \code{fopen} que devuelve un puntero sobre el cual manejar el archivo. Luego para calcular la longitud de éste y poder reservar la cantidad de memoria necesaria, se llama a \code{fseek} para hacer que el puntero apunte al final del archivo y así llamando a \code{ftell}, que devuelve la cantidad de bytes desde el principio del archivo hasta donde esta el puntero, se obtiene el tamaño que se buscaba. Esta cantidad de memoria se reserva usando \code{malloc} y es apuntada con la variable \code{ptr\_buffer}. Finalmente se devuelve el puntero de archivo al principio de éste y se llama a \code{fread}, almacenando en memoria el archivo y se cierra el archivo. \\

En la versión de asm, el funcionamiento es idéntico y no presentó dificultades adicionales. Ya que el proceso es igual para abrir el archivo para descompresión, se escribio una macro en \code{macros.mac} que realiza lo detallado arriba. \\

Esta función tiene que tener almacenados varios datos al mismo tiempo y a su vez tiene varias llamadas a otras funciones que pueden sobreescribir registros (esto se aplica también a funciones externas a nuestra aplicación, como \code{malloc}). Por esta razón la función presenta tantas variables locales, ademas de hacer el código mas declarativo y menos propenso a errores producidos por registros sobreescritos.\\

Luego se llama a \code{comprimir\_buffer}, usando este buffer, el tamaño previamente calculado, y varios punteros para ser rellenados por esta función. La función pide variables del tipo puntero a puntero, en vez de crear este tipo de variables, se crearon punteros comunes y pasamos la dirección de éstos como parametro, usando el C el simbolo \code{\&} y en assembler la instrucción \code{lea}. \\

Al tener la codificación en la variable \code{dst\_buffer}, se pasa a calcular cuantos de estos códigos son válidos para poder crear una tabla de estructuras \code{codificacion\_t} que será escrita en el archivo de salida. Finalmente se crea un header, completandolo con el tamaño original del archivo, la longitud de la codificación, la cantidad de códigos creados y la posición en donde empieza la codificación y es escrito en el archivo de salida junto con la tabla de codificaciones y los datos codificados.\\

La versión en assembler no se diferencia mucho de la de C, porque se trata de llamadas a funciones y calculos y ciclos simples.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{1cm}

\subsection{comprimir\_buffer}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dado un buffer de entrada, comprime los datos contenidos en el.
Devuelve el puntero al buffer con los datos comprimidos, la longitud de este buffer
en bytes, un puntero a la tabla de códigos utilizada para realizar la codificacion y
la longitud en bits de la codificacion. En caso de no poder realizar la compresion
debe retornar un codigo de error.
\end{itemize}

Descripción del algoritmo: \\

Esta función se basa principalmente en llamadas a otras funciones que realizan paso por paso el proceso de compresión. Primero con el buffer de entrada y el tamaño de éste se llama a \code{generar\_tabla\_apariciones} y esa tabla se pasa como parametro a \code{generar\_tabla\_codigos}. Con ambos parametros se llama a \code{calcular\_longitud\_codificacion} que devuelve la longitud de la compresión en bits. Con un cálculo simple se obtiene la longitud en bytes y se reserva la memoria para almacenar la compresión. Finalmente se llama a la función \code{generar\_codificacion} para  guardar los datos comprimidos en la memoria previamente reservada. Se libera la memoria para la tabla de apariciones al terminar la función. \\

Como pasó con la función anterior,en la versión en assembler la cantidad de llamadas a función hace que prefiramos crear muchas variables locales, y la implementación es bastante lineal sin presentar incovenientes.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{generar\_tabla\_apariciones}
Descripción dada por la cátedra:
\begin{itemize}
	\item A partir de un buffer de entrada retorna una tabla de 256 posiciones
donde la posición i contiene la cantidad de apariciones del símbolo i en el buffer.

\end{itemize}

Descripción del algoritmo: \\

		La función recorre byte a byte el buffer donde se encuentra el archivo a comrpimir. Por cada byte que recorre, toma el valor numérico de dicho byte, accede al arreglo “tabla” e incrementa en uno el elemento de la tabla cuyo subíndice corresponda al valor del byte en cuestión. \\

\indent	unsigned int* tabla = (unsigned int*) calloc(256,sizeof(unsigned int)) \\
\indent	int i \\
\indent	for(i=0;i<size;i++) \\
\indent	\indent	tabla[buf[i]]++ \\
\indent	return tabla \\


\subsection{generar\_tabla\_codigos}
Descripción dada por la cátedra:
\begin{itemize}
	\item A partir de la tabla de apariciones, genera la tabla de códigos.

\end{itemize}

\indent	La generación de la tabla de códigos se divide en tres etapas.\\

Primera etapa: Construir la lista de huffman a partir de la tabla de apariciones\\
\indent	Los pasos previos a llamar a la función crear\_lista\_huffman, son crear los parámetros con los cuales la llameremos.
\begin{itemize}

\item 1.El puntero a la tabla de apariciones (al primer elemento del arreglo) la tenemos en la pila, porque es un parámetro de generar\_tabla\_codigos.
\item 2.Necesitamos una variable de tipo nodo\_lista\_t** \\
\end{itemize}

\indent \indent		nodo\_lista\_t ** lista \\
\indent	Al desrefereciarla debería ser NULL, antes de pasarla como parámetro a la función crear\_lista\_huffman. Lo solucionamos de modo similar a lo que hicimos en crear\_arbol\_huffman. Declarando una variable de tipo puntero: nodo\_lista\_t * ptr\_nodo\_lista (que luego del llamado a la función que crea la lista, contendrá la dirección del primero nodo de ésta) \\
Y luego asignádole su dirección a l. De este modo, \\
\indent \indent	nodo\_lista\_t * ptr\_nodo\_lista = NULL \\	
\indent \indent	l = ref( ptr\_nodo\_lista) \\
Al desreferenciarlo tendremos \\
\indent	\indent *l = *(ref (ptr\_nodo\_lista)), que es lo mismo que el valor que toma ptr\_nodo\_lista \\
Es decir,\\
\indent	\indent *l = NULL
\begin{itemize}		
\item 3.La tabla de árboles
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{generar\_codificacion}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dado un buffer de entrada y una tabla de códigos, realiza la codificación y la almacena en el buffer de salida.

\end{itemize}

Descripción del algoritmo: \\

\indent Inicialmente contamos con una variable global de 1 byte de tamaño, byte\_a\_pasar, inicializada en 0. Y otra variable contadora, bits\_agregados, también inicializada en 0.\\
\\
\indent	La función recorre cada byte i del buffer de entrada. Con este byte, se accede a su codificación en la tabla de códigos, que se encuentra en la posición src\_buf[i].\\
\indent	Con un segundo ciclo, recorremos los bits de la codificación reversa, empezando desde el bit menos significativo. Y lo agregamos a la variable byte\_a\_pasar, de la siguiente manera:\\
\begin{itemize}

\item 1.Aplicamos un shift hacia la izquierda, a la representación binaria de byte\_a\_pasar. Le sumamos el bit extraído, para que sea agregado en la posición menos significativa (y que la codificación quede en posición no-reversa).\\
\item 2.Si la variable bits\_agregados era igual a 7, al incrementarla en una unidad, indicará que se ha completado un byte de codificación. Y que el contenido de la variable byte\_a\_pasar deberá ser copiado a la posición de memoria dst\_buf. Hecha la transferencia, se incrementará la dirección del puntero dst\_buf en una unidad, para que apunte al siguiente byte ( al byte contiguo), y se pondrán en 0 byte\_a\_pasar y bits\_agregados.\\
\item 3.Si, en cambio, la variable bits\_agregados era menor que 7, se procederá del mismo modo al momento de copiar el bit de la codificación reversa, pero no se moverá el byte byte\_a\_pasar ni se incrementará el puntero dst\_buf. Y se incrementará la variable bit\_agregados en una unidad (en lugar de reiniciarla a 0)\\
\end{itemize}

\indent	Como bits\_agregados y bytes\_a\_pasar son variables globales, preservan los valores que tuvieron en la iteración anterior. Y están listas para seguir siendo modificadas para agregarles la codificación del siguiente carácter desde la posición en que quedó.\\

\indent El ciclo finaliza cuando se alcanza el byte número src\_size, que está fuera del buffer de entrada.\\
\\
\indent Por último, puede ocurrir que finalice el ciclo y no se hayan completado 8 bits de codificación en byte\_a\_pasar. En este caso, habrá que shifter tantos bits a la izquierda como sean necesarios (8 $–$ bits\_agregados),y  luego mover byte\_a\_pasar a dst\_buf.\\
Esto es para que los bits que pertenecían a la codificación permanezcan contiguos en el buffer de salida, con los que fueron codificados anteriormente.\\
\\
\indent La función devolverá un código de error en caso de que haya ocurrido algún problema al obtener la codificación de un carácter desde la tabla.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{crear\_lista\_huffman}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dada una tabla de apariciones, retorna una lista de arboles. Cada árbol de la lista se corresponde con uno de los símbolos de la tabla cuya cantidad de apariciones es mayor que cero. Los arboles consisten de un solo nodo que está “etiquetado” con el smbolo y la cantidad de apariciones del mismo. La lista está ordenada por la cantidad de apariciones de los smbolos. La funcion también retorna una tabla de 256 posiciones donde la posición “i” tiene un puntero a la hoja del arbol para el símbolo “i” y NULL para aquellos símbolos que no tienen hojas asociadas (es decir, aquellos símbolos cuya cantidad de apariciones es 0). Esta tabla será utilizada luego para generar los códigos de los símbolos.

\end{itemize}

Descripción del algoritmo: \\

El algoritmo utilizado recorre toda la tabla de apariciones buscando los elementos del arreglo cuyo valor sea mayor que cero. Cuando encuentra elemento mayor a cero, reserva memoria para crear un \code{nodo\_lista\_t} y un \code{nodo\_arbol\_t}. Setea el \code{nodo\_arbol\_t} con el símbolo representado por el valor \code{ASCCI} del subindice “i” del arreglo \code{tabla\_apariciones}, las apariciones dadas por \\ \code{tabla\_apariciones[i]}, con \code{VERDADERO} (1) el campo de “valido”, y en los puntero a “padre”, “izq” y “der” en \code{NULL}. Luego Setea el \code{nodo\_lista\_t} con el \code{nodo\_arbol\_t} recien creado y con \code{NULL} en el puntero al siguiente nodo de la lista, y luego mediante la funcion \code{lista\_insetar\_ordenado} agrega el \code{nodo\_lista\_t} recientemente creado y seteado, de forma ordenada de forma creciente según las apariciones del sibolo encontrado. Luego en el arreglo \code{indices\_nodos\_simbolos[i]} agrega "hoja".	\\

\indent		if(tabla\_apariciones[i] $>$ 0) 	\\
\indent	\indent		nodo\_arbol\_t* hoja	\\
\indent	\indent		nodo\_lista\_t* nuevo\_nodo\_lista	\\	
\indent	\indent		hoja $\rightarrow$ símbolo = (char) i			\\
\indent	\indent		hoja $\rightarrow$ apariciones = tabla\_apariciones[i]	\\
\indent	\indent		(hoja $\rightarrow$ izq) = NULL	\\
\indent	\indent		(hoja $\rightarrow$ der) = NULL	\\
\indent	\indent		(hoja $\rightarrow$ padre) = NULL	\\		
\indent	\indent		nuevo\_nodo\_lista $\rightarrow$ nodo\_arbol = hoja \\
\indent	\indent		nuevo\_nodo\_lista $\rightarrow$ sig = NULL \\
\indent	\indent		indices\_nodos\_simbolos = hoja	\\

De caer en un elemento i cuyas apariciones sean nulas, se setea en NULL el el elemento sub i de indices\_nodos\_simbolos \\

\indent		else\\
\indent	\indent		indices\_nodos\_simbolos[i] = NULL \\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{lista\_obtener\_primero}
Descripción dada por la cátedra:

\begin{itemize}
	\item Retorna el primer elemento de la lista (el nodo se quita de la lista) 
\end{itemize}
Descripción del algoritmo: \\

\indent El puntero n está almacenado en la pila. Modificar ese parámetro no cumplirá con lo pedido porque la función que llama a lista\_insertar\_nodo, no accederá al valor contenido allí. Pero sí al puntero *n, al cual esta función puede tener acceso al desreferenciar n. \\
\indent Lo primero que hace el algoritmo es cambiar la dirección a la cual apunta *n, por la dirección del primer nodo de la lista, es decir, *l (al cual se puede acceder de modo análogo a *n, como ya fue explicado, dado que l se encuentra en la pila)\\

\indent	*n = *l \\

\indent	Haciendo esta asignación, se asegura que *n será el primer elemento de la lista. Porque *l era un puntero al primero nodo. \\

\indent	El siguiente y último paso es modificar la lista, para que dicho nodo ya no pertenezca a ella.
Gracias al paso anterior, *n = *l, no perderemos la referencia a éste, por lo tanto bastará con cambiar el puntero al primer elemento, asignándole la dirección del siguiente nodo, al cual podemos acceder por medio del campo sig, del nodo que queremos quitar. \\

\indent	*l = (**l).sig \\
ó \\
\indent	*l = (*l) $\rightarrow$ sig \\

Ni necesitamos el campo sig de **n (el que fue primer elemento) porque ya no haremos uso de él en la función que llamó a lista\_obtener\_primero. Ni el nuevo primer elemento necesitará tener acceso al que fue su anterior. \\


Decisiones tomadas en la implementación en assembler: \\
\indent	Uno de los mayores problemas, ya fue solucionado en la implementación en C: el orden en que alteríamos los punteros. \\
\indent	Ya solucionado como fue detallado arriba, el paso a la implementación en asm le sumó un nuevo desafío: desreferenciar los punteros n y l, y acceder al campo sig del nodo **n \\

La arquitectura IA32 no permitía el direccionamiento indirecto, por lo que cosas como
[parametro\_l\_en\_pila] para desreferenciar l, las tuvimos que hacer con un registro de propósito de general de por medio. \\
\indent	mov ebx, dword parametro\_l\_en\_pila \\
\indent	Teniendo l en un registro, podemos obtener *l con [ebx] \\
\indent	mov esi, dword [ebx] \\
\indent	Ahora tenemos *l en esi \\
La arquitectura IA32 no permitía la transferencia de datos de memoria a memoria con mov
Y tener *n en un registro no modificaría su valor en memoria. \\
Fue solucionado permitiéndole a *n ser accedida de forma directa en memoria, pero a *l tenerla obligatoriamente en un registro (esi, como ya mencionamos): \\
mov edi , dword parametro\_n\_en\_pila \\
\indent	mov [edi], esi	\\
\indent	Es un modo de transferencia válido (registro a memoria) \\

Acceso al campo de una estructura \\
\indent	En esta ocasión, es *l el que tiene que ser accedido de forma directa. Necesariamente tendremos que almacenar (*l)$ightarrow$sig en un registro \\
\indent	mov esi, [esi + offset\_sig] \\
\indent	Ya tenemos en esi el contenido del campo sig, del primer nodo, sólo tenemos que asignárselo a *l.  \\
\indent	Dado que inicialmente teniamos l en ebx, podemos desreferenciarlo así: [ebx] \\
\indent	mov [ebx], esi \\
Y allí finaliza el algoritmo en su implementación en asm \\

Nota: En el registro eax no devolvemos nada, porque la función es de tipo void.
Y debido a que no hizo falta usar más registros de los que se deben salvaguardar por la convención C, tampoco fue necesario salvaguardar eax porque no fue usado \\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{lista\_insertar\_ordenado}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dada una lista y un nodo, inserta el nodo de manera ordenada, de acuerdo a la cantidad de apariciones que indica la raíz del arbol apuntado por el.


\end{itemize}

Descripción del algoritmo: \\

\indent	El algoritmo de inserción distingue tres casos: \\
\indent \indent 1.Insertar el nodo en una lista vacía \\
\indent \indent 2.Insertar el nodo justo delante del primer elemento \\
\indent \indent 3.Insertar el nodo no delante del primer elemento. Esto es, después de algún nodo de la lista. \\

Primer caso: inserción en lista vacía \\
\indent	La lista era vacía, por lo tanto el puntero al primer elemento era un puntero a NULL. \\
\indent	Como no hay otro nodo con el cual comparar cantidad de apariciones, simplemente cambiamos la dirección a la que apunta *l, para que coincida con la dirección del nodo *n (que es el parámetro n pasado por pila) \\

\indent	*l = n \\

\indent	Y para preservar el invariante de lista simplemente enlazada, el último (y único nodo, en este caso) debe valer NULL en su campo sig, pues no hay más elementos. \\
\indent	n $\rightarrow$ sig = NULL \\

\indent	Ambas instrucciones pueden hacerse en cualquier orden, porque son modificaciones de posiciones de memoria independientes entre sí: para asignar n a *l, no necesitamos conocer el valor de n $\rightarrow$ sig; y, del mismo modo, no nos importa saber quien hace referencia a n, antes de hacer la asignación  n $\rightarrow$ sig = NULL \\


Segundo caso: inserción al principio de una lista no vacía. \\
\indent	Se dá cuando tenemos un nodo con el cual comparar apariciones (hago abuso de lenguaje: las comparaciones se hacen entre la cantidad indicada por las raíces de los respectivos nodos árbol a los cuales apunta cada nodo lista) y la cantidad de apariciones de n resulta ser menor que la del primero de la lista. \\

\indent	Se conserva la asignación *l = n, porque ahora n pasa a ser el primero de la lista. Pero a diferencia del caso anterior, el orden importa, porque hay que memorizar la dirección en memoria del nodo que dejará de ser el primero. \\
	
\indent	nodo\_lista\_t * aux = *l \\
\indent	*l = n \\
\indent	n $\rightarrow$ sig = aux \\

Ó modificar primero n $\rightarrow$ sig, si se quiere, para no tener que usar una variable adicional \\
\indent	n $\rightarrow$ sig = *l \\
\indent	*l = n \\

El algoritmo usado, usa la primera forma mencionada: resguarda la dirección *l \\

Tercer caso: insertar después de algún nodo de la lista \\
\indent	Este último caso se dá cuando las apariciones del nodo a insertar no son menores que la del primer nodo lista. \\
\indent	A diferencia de los casos anteriores, el primero de la lista será el mismo que tenía. Pero se mantendrá la idea de cambiar el campo sig del nodo que se insertará. Lo único nuevo es que al haber un nodo anterior a n, habrá que cambiar también su campo sig, no sin antes asignárselo al campo sig de n. En resumen: \\
	
\indent	n $\rightarrow$ sig = ptr\_nodo\_anterior $\rightarrow$ sig \\
\indent	ptr\_nodo\_anterior $\rightarrow$ sig = n \\

\indent	Para llegar a esta instrucción, habrá que recorrer la lista, comparando apariciones hasta que se llegue al final (el siguiente de un nodo sea NULL) ó mientras las apariciones del siguiente sean menores o iguales que las del nodo n. \\
\indent	En cada iteración es necesario recordar la dirección del nodo actual (ptr\_nodo\_anterior), la cual no debe ser NULL, para poder acceder a ptr\_nodo\_anterior  $\rightarrow$ sig, y avanzar de ser necesario. \\


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{crear\_arbol\_huffman}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dada una la lista de  arboles, donde cada arbol consta de un nodo
“etiquetado” con un simbolo y la cantidad de apariciones de ese simbolo, genera
el arbol de Huffman. El proceso consta de generar un nuevo arbol a partir de los
dos primeros  arboles de la lista. El primero de estos pasa a ser el hijo izquierdo y
el segundo el hijo derecho del nuevo arbol creado. Tambien se debe establecer la
cantidad de aparaciones del  arbol recien creado como la suma de las apariciones de
los hijos. Finalmente, este nuevo  arbol se inserta de manera ordenada en la lista.
El proceso se repite hasta que quede un solo arbol.


\end{itemize}

Descripción del algoritmo: \\

\indent	La precondición de la función es que la lista l no sea vacia (esto es, *l distinto de NULL) \\
\indent	Asumiendo eso, sabemos que podemos obtener el primer elemento de lista, al menos una vez.\\
\indent	Aquí se presentan dos casos.\\


\indent	Caso 1: Sólo hay un elemento que podamos extraer.\\
\indent	Al llegar a esta situación, sabremos que el árbol ya estará construido por completo. Sólo debemos asignar  la dirección de memoria del nodo\_arbol\_t (al cual apunta el único nodo de la lista) a la posición de memoria a la cual a hace referencia a, de este modo:\\

\indent	*a = (*l) $\rightarrow$ nodo\_arbol \\

	Y cómo paso final, liberar la memoria reservada para ese nodo lista, ya que no necesitaremos la estructura lista\_huffman una vez que hayamos creado el árbol \\

\indent	Caso 2: Hay al menos dos nodos lista. \\
\indent	Cuando se da este caso, sabemos que podremos llamar a la función listar\_obtener\_primero al menos dos veces. Y así unir los dos árboles a los que apunta cada nodo lista del modo en que se describe arriba.\\

\indent	Usamos variables auxiliares, y le pasamos la dirección que poseen en memoria, para que lista\_obtener\_primero las modifique desreferenciando dichas direcciones. \\
	Esta fue nuestra interpretación: si una variable X es de tipo *Tipo\_De\_Dato, entonces la dirección de X (ref(X)), puede ser tomada como un dato de tipo **Tipo\_De\_Dato (que es lo que necesita la funcion lista\_obtener\_primero) \\

\indent	Luego de llamar la función dos veces, nuestras dos variables de tipo *nodo\_lista\_t son ahora punteros a lo que alguna vez fueron primer y segundo elemento de la lista. \\

\indent	El siguiente paso es reservar memoria para un nuevo nodo\_arbol\_t. Este será la raíz de los árboles a los que apunta cada nodo\_lista\_t extraído. Realizamos las siguientes asignaciones (llamemos primero\_en\_apariciones y segundo\_en\_apariciones al puntero a los nodos extraídos, y nodo\_padre al puntero al bloque de memoria que fue reservado para un nuevo nodo\_arbol\_t): \\

\indent	//El hijo izquierdo de nodo\_padre será el árbol que está en primero\_en\_apariciones y, el derecho, el que está en el segundo\\

\indent	nodo\_padre $\rightarrow$ izq = primero\_en\_apariciones $\rightarrow$ nodo\_arbol \\
\indent	nodo\_padre  $\rightarrow$ der = segundo\_en\_apariciones  $\rightarrow$ nodo\_arbol	\\

\indent	// el puntero al padre de cada subárbol será la dirección en memoria de nodo\_padre \\
\indent	(primero\_en\_apariciones$\rightarrow$nodo\_arbol)$\rightarrow$padre = nodo\_padre \\
\indent	(segundo\_en\_apariciones$\rightarrow$nodo\_arbol)$\rightarrow$padre = nodo\_padre \\
	
\indent	Una vez enlazados correctamente, hay que completar los campos apariciones y valido, de *nodo\_padre \\

\indent	//Como no es un nodo apuntado por alguna posición del arreglo “tabla de árboles” (ni proviene de la lista\_huffman inicial), el contenido del campo símbolo no es válido \\
\indent	nodo\_padre$\rightarrow$valido = 0 \\

\indent	//Pero lo que sí es válido es la cantidad de apariciones. Es la suma de las apariciones indicadas por las raíces de sus hijos\\
\indent	nodo\_padre$\rightarrow$apariciones = (nodo\_padre$\rightarrow$izq)$
ightarrow$ apariciones + (nodo\_padre$\rightarrow$der)$\rightarrow$apariciones \\

\indent	Todos los campos de este nuevo árbol ya están listos. Sólo queda volver a insertarlo en la lista, de forma ordenada. Pero, para ello, crearemos un nuevo nodo\_lista\_t que apunte a este árbol. Y al finalizar (o antes, pero no es el caso de nuestro algoritmo) la inserción de este nodo en la lista, liberaremos el espacio en memoria reservado para los nodos lista extraídos en un principio. Claramente se ve que la cantidad de nodos lista se redujo, pues si bien reservamos memoria por uno, a cambio liberamos la usada por dos. \\

\indent	nuevo\_nodo\_lista$\rightarrow$nodo\_arbol = nodo\_padre \\
\indent	//No es necesario cambiar el campo sig de *nuevo\_nodo\_lista, porque sabemos que de eso se encargará la \\ función que está por llamar, pero no nos gustaría que haya un nodo con un puntero no inicializado. \\
\indent	nuevo\_nodo\_lista$\rightarrow$sig = NULL \\

\indent	Finalmente, llamamos a función lista\_insertar\_ordenado con parámetros l y nuevo\_nodo\_lista. Que da termino a la iteración actual. \\

Notas: \\
1) Al momento de elegir cuál sería la guarda del ciclo, optamos por usar una variable flag que sería cambiada de manera acorde al llegar al Caso1, y haberlo terminado (decidimos que se ingresaría al ciclo cuando valiese 0 y no lo haría una vez que valiese 1)\\

2) Como no teníamos una manera de contar elementos de la lista, pero sabíamos que tendríamos al menos un elemento (por precondición), decidimos que la primer llamada a lista\_obtener\_primero sería compartida por los dos casos. Y para evaluar en cuál de los dos nos encontrábamos, sólo teníamos que preguntar si la lista había quedado vacía o no.\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{generar\_codigo}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dado un  arbol de Huffman y un puntero a la hoja asociada al
sımbolo para el cual se quiere obtener el codigo, recorre el  arbol y retorna el codigo.
Si la longitud del codigo generado es mayor a 32 bits, la funcion debe terminar y
retornar un codigo de error.


\end{itemize}

Descripción del algoritmo:

		La función comienza veirificando si el arbol de huffman es vacío, en cuyo caso llena el campo del codig
\_t “valido” en FASO (0), y retorna 0, que es el numero del código de error.
		Luego se genera un arreglo de 32 enteros, y se los setea en 0. Con el arreglo “codigo” creado y con sus elementos en 0, entra en un ciclo que recorrera el arbol desde la hoja del símbolo a codificar hasta la raiz, que iterara 32 veces o hasta llegar a la raiz.Al comenzar, me situo en la hoja asociada al símbolo y pregunto si es raíz, es decir, si su padres es NULL. Si lo es, sale del ciclo que recorre el arbol, sino, pregunta si es hijo izquierdo o derecho de su padre. Si es hijo derecho, pongo un 1 en el arreglo “codigo” con subindice “i”, donde “i” es el numero de iteracion en el ciclo que recorre el arbol. De ser hijo izquierdo, pongo un 0 en el arreglo codigo[i]. Luego me desplazo hacia el padre, aumento en uno mi contador de iteraciones, y vuelvo a comenzar.

\indent		nodo\_arbol\_t*  iter = hoja	\\
\indent		int tam=0		\\
\indent		while(tam$<$32)		\\
\indent	\indent		if(iter $\rightarrow$ padre==NULL) \\
\indent	\indent \indent		break \\
\indent	\indent		if(iter == ((nodo\_arbol\_t*)(iter$
ightarrow$padre)) $\rightarrow$ izq) \\
\indent	\indent	\indent		codigo[tam]=0 \\
\indent	\indent		else  \\
\indent	\indent	\indent		codigo[tam]=1 \\
		
\indent	\indent		tam = tam+1 \\
\indent	\indent		iter=iter $\rightarrow$ padre \\
		
		Una vez con el código escrito en el arreglo “codigo”, tengo que preguntar si es un código valido, o si son los primeros 32 bits de un codigo aun mas largo, con lo cual verifico que el contador tam sea menor que 32. Si es igual a 32 (que como el arreglo va de 0 a 31, seria el bit  numero 33), cargo en el campo “valido” del codigo\_t un FALSO (0), y devuelvo 0. \\

\indent			if tam == 32 \\
\indent	\indent			c $\rightarrow$ valido = 0 \\
\indent	\indent			return 0 \\

		Teniendo ahora si un código efectivamente valido, debemos setear el codigo\_t con el código, el reverso del código, la longitud del código, y si este es válido o no. Para ello, debemos transformar el arreglo “codigo”, en un numero de 32 bits que contenga los bits del código en el mismo orden que el arreglo y luego en el orden inverso. Creamos dos enteros, codigo\_derecho, y codigo\_reverso en cero. Luego tomamos el primer elemento del arreglo y me guardo en codigo\_derecho un \code{OR} ente los 32 bits de codigo\_derecho y codigo[1]. Luego, shifteo un lugar a la izquierda codigo\_derecho y repito o mismo con codigo[2]. De esta forma, itero “tam” veces y voy acomodando en codigo\_derecho bit a bit los elementos válidos del arreglo “codigo”. Para setear codigo\_reverso se hace de la misma forma, pero en lugar de en la iteración numero “j” hacer un \code{OR} con el elemento codigo[j], hago un \code{OR} con el elemento codigo[tam-j-1], y asi recorro el arreglo desde el ultimo elemento válido hasta el primero. Luego guardo los valores en el codigo\_t y devuelvo un 1 indicando que no hubo error. \\

\indent	int j=0; \\
\indent	unsigned int codigo\_derecho=0; \\
\indent	unsigned int codigo\_reves=0; \\
\indent	while(j$<$tam) \\ 
\indent	\indent	codigo\_reves = (codigo\_reves*2)+codigo[j]; \\
\indent	\indent	codigo\_derecho = (codigo\_derecho*2)+codigo[tam-j-1]; \\
\indent	\indent	j = j$+$1; \\
\indent	c $\rightarrow$ codigo = codigo\_derecho; \\	
\indent	c $\rightarrow$ codigo\_rev = codigo\_reves; \\
\indent	c $\rightarrow$ long\_codigo = tam; \\
\indent	c $\rightarrow$ valido = 1; \\
\indent	return 1;  \\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	

\subsection{calcular\_longitud\_codificacion}

Descripción dada por la cátedra:
\begin{itemize}
	\item Retorna la longitud de la codificacion.
\end{itemize}

Descripción del algoritmo: \\

		La función recorre la tabla de apariciones, y en cada elemento “i” que aparezca al menos una vez, multiplica esa cantidad de operaciones por la longitud del codigo del elemento “i” y lo acumula. Luego devuelve ese acumulador \\
		

\indent		int res=0 \\
\indent		int i \\
\indent		for(i=0;i$<$256;i++) \\
\indent \indent		if (tabla\_apariciones[i] ) \\
\indent \indent \indent		res $+$= tabla\_codigo[i].long\_codigo*tabla\_apariciones[i] \\
\indent		return res\\
		
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{generar\_codificacion}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dado un buffer de entrada y una tabla de codigos, realiza la codifi-
cacion y la almacena en el buffer de salida.
\end{itemize}

Descripción del algoritmo: \\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{descomprimir\_archivo}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dado un archivo de entrada, lo carga en un buffer, lo descomprime
y lo guarda en el archivo de salida. En caso de no poder realizar la compresion
debe retornar un codigo de error.

\end{itemize}

Descripción del algoritmo: \\

Para descomprimir el archivo, se abre y se guarda en un buffer igual como se hizo en la función \code{comprimir\_archivo}. Incluso en la versión de assembler, se utiliza la misma macro que fue llamada para \code{comprimir\_archivo}. Al tener el archivo comprimido en memoria, se llama a \code{cargar\_tabla\_codigo\_desde\_buffer}, que transforma las tablas de \code{codificacion\_t} incluidas en el buffer en tablas de \code{codigo\_t} y asi se llama a la función principal \code{descomprimir\_buffer}. Una vez descomprimido y almacenado en memoria usando \code{dst\_buffer} como puntero, se escribe el buffer entero en un archivo de salida.\\

Como sucedia antes, la implementación en assembler no presentó mas dificultades que tener que utilizar varias variables locales.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{descomprimir\_buffer}
Descripción dada por la cátedra:
\begin{itemize}
	\item Dado un buffer y una tabla de codigos realiza la decodificacion y
pone el resultado en el buffer de salida.

\end{itemize}

Descripción del algoritmo: \\

Esta función se encargará del proceso real de descompresión. A partir de la tabla de códigos se llama a \code{cargar\_arbol\_huffman}, que devuelve el arbol que se utilizará  para recorrer el buffer y decodificar los datos. Un problema que se presentó en toda la función fue el manejo de punteros y punteros dobles, que fueron resueltos con una combinación de instrucciones \code{lea} y \code{mov} según fuera necesario. \\

Para el proceso de descompresión, se carga un byte del buffer, y por cada bit, se recorre el árbol creado anteriormente. Empezando por la raíz si el bit leido tiene valor 1, se pasa al nodo izquierdo  y sino al derecho. Si este nodo no existe, es porque el puntero se encuentra en una hoja del árbol, lo cual significa que hay un código valido. Este se lee y se escribe en el buffer de salida y se repite el proceso desde la raíz. \\

En la implementación en C, se creó una estructura llamada Bit, que representa un \code{bitfield} de un solo bit. Al pasarle un entero, esta estructura se queda con su ultimo bit que es el que usamos para recorrer el arbol. Luego de recorrer hacia el siguiente nodo, se divide por dos el número original para poder tomar el siguiente bit.\\
En assembler se utilizaron shifts para dividir al numero y un \code{and} con el valor 1 y el número original para saber el valor del último byte. Se usan variables locales para los principales datos, como el puntero a la raíz que es un dato que no podemos arriesgarnos a perder sobreescribiendo un registro. Al final de la función se libera la memoria requerida por el árbol con la función \code{borrar\_arbol}.\\

Esta función presenta el calculo del porcentaje al igual que al comprimir. En C se llama a printf varias veces, mientras que en assembler se llama una sola vez por ciclo y en cada llamada se limpia el buffer usando \code{fflush}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{cargar\_tabla\_codigo\_desde\_buffer}
Descripción dada por la cátedra:
\begin{itemize}
	\item Cargar la tabla de codigos a partir del buffer de entrada.

\end{itemize}

Descripción del algoritmo: \\

Esta función toma el buffer comprimido, que contiene todos los códigos guardados en una tabla de estructuras \code{codificacion\_t}, y forma la tabla de códigos a partir de esta. Se reserva memoria para una tabla de \code{codigo\_t} de tamaño 256, usando la función \code{calloc}, que reserva memoria y a su vez, la inicializa en cero. Cada estructura \code{codificacion\_t} tiene guardado un caracter, su código codificado, y la longitud de éste (sin esta longitud no se sabría cuantos ceros hay antes del primer 1 del código). Si llamo al caracter como "i", tengo que guardar los datos en tabla\_codigo[i]. Ya tenemos el codigo y la longitud, faltan los campos \code{codigo\_rev} y \code{valido}. Para \code{codigo\_rev} se realiza un ciclo simple que transforma en base a divisiones, modulos y multiplicaciones al código original en su reverso, y el campo \code{valido} simplemente se inicializa en 1.\\
Se realiza este proceso para cada codificación guardada en el buffer. Podemos asumir que todas estas codificaciones pertenecen a códigos diferentes, entonces no se sobreescribirán datos en tabla\_codigos.\\

En assembler, la mayoria de los errores surgidos de esta función fueron a partir del manejo de punteros dobles. Mas alla de eso, no hubo complicaciones, se utilizaron shifts lógicos para multiplicar y dividir por 2. Un shift aritmético no fue necesario ya que todos los datos sin no signados.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{cargar\_arbol\_huffman}
Descripción dada por la cátedra:
\begin{itemize}
	\item Cargar el arbol de Huffman a partir del buffer de una tabla de
codigos. El  arbol de Huffman se utilizara para facilitar el proceso de descompresion.

\end{itemize}

Descripción del algoritmo: \\

Primero creamos la raiz del árbol. Creamos un nodo\_arbol\_t llamado raíz, seteamos sus punteros a padre, izq y der en NULL, y le asignamos FALSO (0) en el campo “valido”.\\ 
		Luego recorremos la tabla de códigos elemento por elemento de los 256. Si el elemento sub “i” tiene un 0 en el campo de “valido”, no se hace nada y se aumenta “i”. Si se encuentra un elemento cuyo campo “valido” sea igual a 1, me guardo de ese codigo\_t su longitud,  su código reverso. Luego itero una cantidad de veces igual a la longitud almacenada armando el árbol con esa codificación. Para hacer esto, verificamos si codigo\_reverso es par o impar (si su ultimo bit es 0 o 1). Si es 1, es decir, impar, voy a la raíz, y me voy a su hijo izquierdo. Si había un nodo colgando, me paro ahí. Si no lo había, lo creo de la misma forma que creamos el noto\_arbol\_t, sólo que en el campo “padre” le asignamos la raíz, y luego me paro en este nuevo nodo. A continuación decremento en un la longitud del codigo y se shiftea hacia la derecha codigo\_reverso, es decir, se lo divide por 2 con división entera, y se vuelve a iterar. De forma análoga se opera si codigo\_reverso era par, sólo que en lugar de ir a la izquierda voy a la derecha. \\
\indent	int tam =0 \\
\indent	while(tam$<$256) \\
\indent \indent	if(tabla\_codigos[tam].valido == 1) \\
\indent \indent \indent	int tam\_camino=tabla\_codigos[tam].long\_codigo; \\
\indent \indent \indent	unsigned int camino = tabla\_codigos[tam].codigo\_rev \\
\indent \indent \indent	nodo\_arbol\_t* iter = raiz;			\\
\indent \indent \indent	while(tam\_camino>0)	\\
\indent \indent \indent \indent	int paridad=camino mod 2; \\				
\indent \indent \indent \indent	if(paridad==1)	\\
\indent \indent \indent \indent \indent	if(iter $\rightarrow$ izq == NULL)\\
\indent \indent \indent \indent \indent \indent	nodo\_arbol\_t*  nuevo\_nodo =new nodo\_arbol\_t \\   
\indent \indent \indent \indent \indent \indent	iter $\rightarrow$ izq = nuevo\_nodo;\\
\indent \indent \indent \indent \indent \indent	nuevo\_nodo $\rightarrow$ valido = 0;\\
\indent \indent \indent \indent \indent \indent nuevo\_nodo$\rightarrow$padre = iter;\\
\indent \indent \indent \indent \indent \indent	nuevo\_nodo $\rightarrow$ izq = NULL;\\
\indent \indent \indent \indent \indent \indent	nuevo\_nodo $\rightarrow$ der = NULL;\\
\indent \indent \indent \indent \indent \indent	iter = iter $\rightarrow$ izq;\\
\indent \indent \indent \indent \indent	else\\
\indent \indent \indent \indent \indent \indent	iter = iter $\rightarrow$ izq\\
\indent \indent \indent \indent else \\
\indent \indent \indent \indent \indent	if(iter $\rightarrow$ der == NULL) // idem pero si el ultimo biy es 1...	\\
\indent \indent \indent \indent \indent \indent	nodo\_arbol\_t* nuevo\_nodo= new nodo\_arbol\_t	\\
\indent \indent \indent \indent \indent \indent	iter $\rightarrow$ der = nuevo\_nodo;	\\
\indent \indent \indent \indent \indent \indent	nuevo\_nodo $\rightarrow$ valido = 0;	\\
\indent \indent \indent \indent \indent \indent	nuevo\_nodo $\rightarrow$ padre = iter;	\\
\indent \indent \indent \indent \indent \indent	nuevo\_nodo $\rightarrow$ izq = NULL;	\\
\indent \indent \indent \indent \indent \indent	nuevo\_nodo $\rightarrow$ der = NULL;	\\
\indent \indent \indent \indent \indent \indent iter = iter $\rightarrow$ der;	\\
\indent \indent \indent \indent \indent else	\\
\indent \indent \indent \indent \indent 	iter = iter $\rightarrow$ der;	\\
\indent \indent \indent	tam\_camino = tam\_camino - 1	\\
\indent \indent \indent	camino = camino/2	\\
\indent tam++	\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{borrar\_arbol}
Descripción de la función: \\
\begin{itemize}


	
\item	Libera la memoria ocupada por el árbol apuntado por un puntero.
\end{itemize}

Descripción del algoritmo: \\

	Libera la memora asignada a cada nodo del árbol apuntado por a, de forma recursiva.\\
	Si a es NULL, no hay memoria que liberar. Éste es el caso base.\\
	Si a apunta a un nodo árbol, es decir, a la raíz de ese árbol, se llama si misma para liberar los nodos de cada subárbol del nodo actual y, finalmente libera memoria del nodo árbol raíz. Para ello hacemos uso de la función free.\\

\indent	if (a != NULL) \\
\indent \indent	borrar\_arbol (a $\rightarrow$ izq);	//borra subárbol izquierdo \\
\indent \indent	borrar\_arbol (a $\rightarrow$ der);	//borra subárbol derecho   \\
\indent \indent	free(a);					//libera nodo raíz \\
	



\pagebreak
